{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第1关：实现kNN算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#encoding=utf8\n",
    "import numpy as np\n",
    "\n",
    "class kNNClassifier(object):\n",
    "    def __init__(self, k):\n",
    "        '''\n",
    "        初始化函数\n",
    "        :param k:kNN算法中的k\n",
    "        '''\n",
    "        self.k = k\n",
    "        # 用来存放训练数据，类型为ndarray\n",
    "        self.train_feature = None\n",
    "        # 用来存放训练标签，类型为ndarray\n",
    "        self.train_label = None\n",
    "\n",
    "\n",
    "    def fit(self, feature, label):\n",
    "        '''\n",
    "        kNN算法的训练过程\n",
    "        :param feature: 训练集数据，类型为ndarray\n",
    "        :param label: 训练集标签，类型为ndarray\n",
    "        :return: 无返回\n",
    "        '''\n",
    "\n",
    "        #********* Begin *********#\n",
    "        self.train_feature = feature\n",
    "        self.train_label = label\n",
    "        #********* End *********#\n",
    "\n",
    "\n",
    "    def predict(self, feature):\n",
    "        '''\n",
    "        kNN算法的预测过程\n",
    "        :param feature: 测试集数据，类型为ndarray\n",
    "        :return: 预测结果，类型为ndarray或list\n",
    "        '''\n",
    "\n",
    "        #********* Begin *********#\n",
    "        m = len(feature)\n",
    "        label = list(set(self.train_label))\n",
    "        res = np.zeros(shape=(m, 1))\n",
    "\n",
    "        for i in range(0, m):\n",
    "            # 计算第i个样本到其他所有样本的距离\n",
    "            dis = np.sqrt(np.sum((feature[i, :] * self.train_feature)**2, axis=1))\n",
    "            idx = np.argsort(dis)\n",
    "            # sort_dis = dis[idx]\n",
    "            sort_label = self.train_label[idx]\n",
    "\n",
    "            score = np.zeros(shape=(len(label), 1))\n",
    "            for j in range(0, self.k):\n",
    "                score[sort_label[j]] += 1\n",
    "\n",
    "            res[i] = np.argmax(score)\n",
    "\n",
    "            dictionary = dict(zip(sort_label, [0]*len(sort_label)))\n",
    "            for j in range(0, self.k):\n",
    "                dictionary[sort_label[j]] += 1\n",
    "            \n",
    "            res[i] = max(dictionary, key=lambda k: dictionary[k])  \n",
    "            \n",
    "        return res\n",
    "\n",
    "        #********* End *********#\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#encoding=utf8\n",
    "import numpy as np\n",
    "\n",
    "class kNNClassifier(object):\n",
    "    def __init__(self, k):\n",
    "        '''\n",
    "        初始化函数\n",
    "        :param k:kNN算法中的k\n",
    "        '''\n",
    "        self.k = k\n",
    "        # 用来存放训练数据，类型为ndarray\n",
    "        self.train_feature = None\n",
    "        # 用来存放训练标签，类型为ndarray\n",
    "        self.train_label = None\n",
    "        \n",
    "\n",
    "    def fit(self, feature, label):\n",
    "        '''\n",
    "        kNN算法的训练过程\n",
    "        :param feature: 训练集数据，类型为ndarray\n",
    "        :param label: 训练集标签，类型为ndarray\n",
    "        :return: 无返回\n",
    "        '''\n",
    "        #********* Begin *********#\n",
    "        self.train_feature = np.array(feature)\n",
    "        self.train_label = np.array(label)\n",
    "        #********* End *********#\n",
    "    def predict(self, feature):\n",
    "        '''\n",
    "        kNN算法的预测过程\n",
    "        :param feature: 测试集数据，类型为ndarray\n",
    "        :return: 预测结果，类型为ndarray或list\n",
    "        '''\n",
    "        #********* Begin *********#\n",
    "        def _predict(test_data):\n",
    "            distances = [np.sqrt(np.sum((test_data - vec) ** 2)) for vec in self.train_feature]\n",
    "            nearest = np.argsort(distances)\n",
    "            topK = [self.train_label[i] for i in nearest[:self.k]]\n",
    "            votes = {}\n",
    "            result = None\n",
    "            max_count = 0\n",
    "            for label in topK:\n",
    "                if label in votes.keys():\n",
    "                    votes[label] += 1\n",
    "                    if votes[label] > max_count:\n",
    "                        max_count = votes[label]\n",
    "                        result = label\n",
    "                else:\n",
    "                    votes[label] = 1\n",
    "                    if votes[label] > max_count:\n",
    "                        max_count = votes[label]\n",
    "                        result = label\n",
    "            return result\n",
    "        predict_result = [_predict(test_data) for test_data in feature]\n",
    "        return predict_result\n",
    "        #********* End *********#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第2关：红酒分类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "from sklearn.preprocessing import StandardScaler\n",
    "\n",
    "def classification(train_feature, train_label, test_feature):\n",
    "    '''\n",
    "    对test_feature进行红酒分类\n",
    "    :param train_feature: 训练集数据，类型为ndarray\n",
    "    :param train_label: 训练集标签，类型为ndarray\n",
    "    :param test_feature: 测试集数据，类型为ndarray\n",
    "    :return: 测试集数据的分类结果\n",
    "    '''\n",
    "\n",
    "    #********* Begin *********#\n",
    "    scaler = StandardScaler()\n",
    "    train_feature = scaler.fit_transform(train_feature)\n",
    "    test_feature = scaler.transform(test_feature)\n",
    "    clf = KNeighborsClassifier()\n",
    "    clf.fit(train_feature, train_label)\n",
    "    return clf.predict(test_feature)\n",
    "    #********* End **********#"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tf38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.19"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
